import java.io.*;


public class DynamicAligner {
	
	public DynamicAligner(){
		
		
	}
	
	int align(String x, String y){
		/*
m = length(X)
 n = length(Y)
c = int[m+1][n+1] for i=0:m
c[i, 0] = 0 for j=1:n
c[0, j] = 0 for i=1:m
for j=1:n
if X[i-1] = Y[j-1]
d =0
else
d =1
end if
c[i, j] = min( c[i-1, j-1] + d, c[i-1, j] + 1, c[i, j-1] + 1 )
end for end for
return c[m, n]
		 */
		
		int m=x.length();
		int n=y.length();
		int[][] c = new int[m+1][n+1];
		// < || <= ???
		for(int i=0; i<=m; i++){
			c[i][0]=0;		
		}
		for(int j=1; j<=n; j++){
			c[0][j]=0;		
		}
		
		for(int i=1; i<=m; i++){
			for(int j=1; j<=n; j++){
				int d=0;
				if(x.charAt(i-1) != y.charAt(j-1))
					d=1;
				int min = (c[i-1][j-1] + d < c[i-1][j] + 1) ? c[i-1][j-1] + d : c[i-1][j] + 1;
				min = (min < c[i][j-1] + 1 ) ? min : c[i][j-1] + 1  ;
				c[i][j]= min;
			}
		}	

		
		return c[m][n];
	}

}
